#ifndef __BTREE_H__
#define __BTREE_H__

typedef struct BTreeNode {
    // 数据
    int data;
    // 左右子树的指针
    struct BTreeNode* left;
    struct BTreeNode* right;
} BTreeNode;

typedef struct BTree {
    // 指向树的根节点的指针
    BTreeNode *root;
} BTree;

typedef void(*tree_visitor)(BTreeNode*);

/**
 * 新创建一颗空树
 * @return 返回空树的指针
 */
extern BTree *new_tree();

/**
 * 新创建一个节点
 * @param val 节点的值
 * @return 新节点指针
 */
extern BTreeNode *new_node(int val);

/**
 * 给节点添加左孩子节点
 * @param node 节点
 * @param val 要添加的孩子节点的值
 * @return 左孩子节点的指针
 */
extern BTreeNode *add_left_child(BTreeNode *node, int val);

/**
 * 给节点添加右孩子节点
 * @param node 节点
 * @param val 要添加的孩子节点的值
 * @return 右孩子节点的指针
 */
extern BTreeNode *add_right_child(BTreeNode *node, int val);

/**
 * 递归的方式前序遍历二叉树
 * @param btree 二叉树
 */
extern void preorder_visit_r(BTree *btree, tree_visitor visitor);

/**
 * 递归的方式中序遍历二叉树
 */
extern void inorder_visit_r(BTree *btree, tree_visitor visitor);

/**
 * 递归的方式后序遍历二叉树
 */
extern void postorder_visit_r(BTree *btree, tree_visitor visitor);

/**
 * 非递归方式后序遍历二叉树
 */
extern void preorder_visit(BTree *btree, tree_visitor visitor);

/**
 * 以层序遍历二叉树
 */
extern void level_visit(BTree *btree, tree_visitor visitor);

/**
 * 求树的深度
 */
extern int tree_height(BTree *bree);

#endif